Heaps: Building a Heap from an Array

What if we are given an unsorted array and want to turn it into a valid heap?

Naive Approach: Create an empty heap and insert each element one by one. The cost for inserting the $i$-th element is $O(\log i)$, as the element may need to "bubble up" to the root.
The total cost is the sum of inserting each of the $n$ elements: \[ \text{Cost} = \sum_{i=1}^{n} O(\log i) = O(\log 1 + \log 2 + \dots + \log n) \] This sum is bounded by $n \times O(\log n)$, giving a total complexity of $O(n \log n)$.
Efficient Approach: A specialized algorithm called heapify allows us to build the heap in-place with a much better time complexity: $O(n)$ time!

Key Takeaway

While repeated insertion works, a linear-time `heapify` algorithm is significantly more efficient for building a heap from an existing collection of elements.

Naive Approach: Repeated Insertions

$$O(n \log n)$$

Cost

Elements (n)

Efficient Approach: Heapify

$$O(n)$$

Cost

Node Index (from n/2 down to 0)